package sort.quick;

public class quick_sort {
    public static void main(String[] args) {
        int[] s = new int[]{8, 9, 3, 2, 1, 4, 6, 9, 5};
        quick_sort(s, 0, s.length - 1);
        for (int x :
                s) {
            System.out.print(x+" ");
        }
    }


    public static void quick_sort(int[] nums, int start, int end) {
        if (start < end) {
            int base = nums[start];
            int left = start;
            int right = end;
            while (left < right) {
                while (left < right && nums[right] >= base) {//nums[right] 比 base大，right--
                    right--;
                }
                //nums[right]比base小,换left
                nums[left] = nums[right];

                while (left < right && nums[left] <= base) {//nums[left] 比 base小，left++;
                    left++;
                }
                //nums[left]比base大
                nums[right] = nums[left];
            }
            nums[left] = base;
            quick_sort(nums, start, left - 1);
            quick_sort(nums, left + 1, end);
        }

    }
}
